package sortAlgorithm;


public class SortAlgorithms {
	/**
	 * 锟斤拷选锟斤拷锟斤拷锟斤拷
	 * @param arr
	 */
	public void simpleSelect(int arr[]) {
		for(int i=0;i<arr.length;i++) {
			int value = arr[i];
			int position = i;
			for(int j = i + 1; j<arr.length;j++) {
				if(arr[j]<value) {
					value = arr[j];
					position =j;
				}
			}
			//锟斤拷锟斤拷
			arr[position] = arr[i];
			arr[i] =value;
		}
	}
	
	/**
	 * 直锟接诧拷锟斤拷锟斤拷锟斤拷
	 * @param arr
	 */
	public void directInsert(int arr[]) {
		for(int i=1;i<arr.length;i++) {
			int j = i-1;
			int inserNum = arr[i];
			while(j>=0 && arr[j]>inserNum) {
				arr[j+1]  = arr[j];
				j--;
			}
			arr[j+1] = inserNum;//注锟斤拷锟斤拷锟斤拷锟揭�+1锟斤拷锟斤拷
		}
	}
	
	/**
	 * 希锟斤拷锟斤拷锟斤拷
	 * @param arr
	 */
	public void shellSort(int arr[]) {
		int len = arr.length;
		while(len>=1) {
			for(int i=len;i<arr.length;i++) {
				int j = i -len;
				int insertNum = arr[i];
				while(j>=0 && arr[j]>arr[i]) {
					arr[j+1] =arr[j];
					j -=len;
				}
				arr[j+len] =insertNum;
			}
			len /=2;
			
		}
	}
	
	 public  void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp锟斤拷锟角伙拷准位
        temp = arr[low];

        while (i<j) {
            //锟饺匡拷锟揭边ｏ拷锟斤拷锟斤拷锟斤拷锟斤拷菁锟�
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //锟劫匡拷锟斤拷撸锟斤拷锟斤拷锟斤拷锟斤拷业锟斤拷锟�
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷蚪换锟�
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //锟斤拷蠼锟阶嘉拷锟絠锟斤拷j锟斤拷锟轿伙拷玫锟斤拷锟斤拷纸锟斤拷锟�
         arr[low] = arr[i];
         arr[i] = temp;
        //锟捷癸拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷
        quickSort(arr, low, j-1);
        //锟捷癸拷锟斤拷锟斤拷野锟斤拷锟斤拷锟�
        quickSort(arr, j+1, high);
    }
	
	 /**
	  * 褰掑苟鎺掑簭
	  * @param arr
	  * @param l
	  * @param r
	  */
	 public  void mergSort(int [] arr,int l,int r){
        if(l>=r) return;
        int mid = (l+r)/2;
        //閫掑綊浜屽垎 灏嗘暟缁勫垎涓�  [宸�,涓璢,(涓�,鍙砞
        mergSort(arr,l,mid);
        mergSort(arr,mid+1,r);
        //褰掑苟鎺掑簭
        int aux[] = new int[r-l+1]; //杩欓噷寮勪竴涓澶勭悊鐨勬暟缁勫壇鏈� 闀垮害鏄� R-L+1 
        for (int i =l;i<=r ;i++)    //鍓湰鏁扮粍浠� L 寮�濮嬶紝鎵�浠ヤ笌鍘熸暟缁勫瓨鍦ㄤ竴涓� L 鐨勫亸绉婚噺
            aux[i-l] = arr[i];
        int i = l,j = mid+1;        //i璁板綍宸﹁竟鍏冪礌鐨勪笅鏍囦綅缃� j璁板綍鍙宠竟鍏冪礌鐨勪笅鏍囦綅缃�
        for (int k =l;k <= r; k++){ //k璁板綍 arr 鐨勪笅鏍囦綅缃�
            if(i >mid){
                arr[k] = aux[j-l];
                j++;
            }else if(j >r){
                arr[k] = aux[i-l];
                i++;
            }else if(aux[i-l] < aux[j-l]){
                arr[k] = aux[i-l];
                i++;
            }else{
                arr[k] = aux[j-l];
                j++;
            }
        }
	  }
	 
	public static void main(String[] args) {
		
		SortAlgorithms sort = new SortAlgorithms();

		int arrs[] = {4,3,6,5,1,7,2};
		System.out.println("原始数组:");
		for(int i:arrs) {
			System.out.print(i + ", ");
			
		}
		System.out.println();

		sort.quickSort(arrs,0,arrs.length-1);
		System.out.println("快速排序:");
		for(int i:arrs) {
			System.out.print(i + ", ");
		}
	}

}
